//给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [1,3,null,null,2]
//输出：[3,1,null,null,2]
//解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
// 
//
// 示例 2： 
//
// 
//输入：root = [3,1,4,null,null,2]
//输出：[2,1,4,null,null,3]
//解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。 
//
// 
//
// 提示： 
//
// 
// 树上节点的数目在范围 [2, 1000] 内 
// -2³¹ <= Node.val <= 2³¹ - 1 
// 
//
// 
//
// 进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？ 
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树 👍 757 👎 0


package com.cjl.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * [P99]_恢复二叉搜索树
 *
 * @author cjl
 * @date 2022-07-23 16:32:08
 */
public class P99_RecoverBinarySearchTree {
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P99_RecoverBinarySearchTree().new Solution();
        TreeNode t1 = new TreeNode(-33, null, null);
        TreeNode t2 = new TreeNode(321, t1, null);
        TreeNode t3 = new TreeNode(55, t2, null);
        TreeNode t4 = new TreeNode(71, t3, null);
        TreeNode t5 = new TreeNode(231, null, null);
        TreeNode t6 = new TreeNode(399, null, null);
        TreeNode t7 = new TreeNode(-13, t5, t6);
        TreeNode t8 = new TreeNode(146, t4, t7);
        solution.recoverTree(t8);
    }
    //力扣代码
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    class Solution {
        /**
         * 一遍：二叉搜索树 前序遍历递增；
         * 找到有问题的两个节点，交换位置
         *
         * @param root
         */
        public void recoverTree(TreeNode root) {
            List<TreeNode> treeNodeList = new ArrayList<>();
            qianxubianli(root, treeNodeList);
            //遍历查找有问题的节点
            TreeNode t1 = null;
            TreeNode t2 = null;
            if (treeNodeList.get(0).val > treeNodeList.get(1).val) {
                t1 = treeNodeList.get(0);
            }
            for (int i = 1; i < treeNodeList.size() - 1; i++) {
                //非连续两个节点和连续节点有问题共性：
                // 第一次出现前一个大于左右值，边线节点可不判断对应的边
                // 最后一次出现后一个小于左右两个值(连续两个值交换，应该只出现一次小于两侧值，非连续会出现两次，后一次才是需要替换的)，边线节点可不判断对应的边
                if (t1 == null && treeNodeList.get(i).val > treeNodeList.get(i + 1).val && treeNodeList.get(i).val > treeNodeList.get(i - 1).val) {
                    t1 = treeNodeList.get(i);
                }
                if (treeNodeList.get(i).val < treeNodeList.get(i + 1).val && treeNodeList.get(i).val < treeNodeList.get(i - 1).val) {
                    t2 = treeNodeList.get(i);
                }
            }
            //注意这个判定时机，容易出错
            if (treeNodeList.get(treeNodeList.size() - 1).val < treeNodeList.get(treeNodeList.size() - 2).val) {
                t2 = treeNodeList.get(treeNodeList.size() - 1);
            }
            int tmp = t1.val;
            t1.val = t2.val;
            t2.val = tmp;
        }

        public void qianxubianli(TreeNode root, List<TreeNode> treeNodeList) {
            if (root.left != null) {
                qianxubianli(root.left, treeNodeList);
            }
            treeNodeList.add(root);
            if (root.right != null) {
                qianxubianli(root.right, treeNodeList);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}